/**
 * 395. 至少有 K 个重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */

// /**
//  * @param {string} s
//  * @param {number} min
//  * @return {number}
//  */
// function longestSubstring(s, min) {
//   if (min < 2) {
//     return s.length;
//   }
//   if (s.length < min) {
//     return 0;
//   }
//   const indexesMap = new Map();
//   const chars = [];
//   for (let i = 0; i < s.length; i += 1) {
//     const code = s.charCodeAt(i);
//     let indexes = indexesMap.get(code);
//     if (!indexes) {
//       indexes = new Array(s.length).fill(false);
//       indexesMap.set(code, indexes);
//
//       chars.push(code);
//     }
//     indexes[i] = true;
//   }
//   const countsMap = new Map();
//   for (let i = 0; i < chars.length; i += 1) {
//     const code = chars[i];
//     const indexes = indexesMap.get(code);
//     const counts = new Array(s.length).fill(indexes[0] ? 1 : 0);
//     for (let j = 1; j < s.length; j += 1) {
//       if (indexes[j]) {
//         counts[j] = counts[j - 1] + 1;
//       } else {
//         counts[j] = counts[j - 1];
//       }
//     }
//     countsMap.set(code, counts);
//   }
//   let max = 0;
//   for (let i = 0; i < s.length; i += 1) {
//     for (let j = i - (max < min ? (min - 1) : max); j >= 0; j -= 1) {
//       let flag = true;
//       for (let k = 0; k < chars.length; k += 1) {
//         const indexes = indexesMap.get(chars[k]);
//         const counts = countsMap.get(chars[k]);
//         const count = counts[i] - counts[j] + (indexes[j] ? 1 : 0);
//         if (count && count < min) {
//           flag = false;
//           break;
//         }
//       }
//       if (flag) {
//         max = Math.max(max, i - j + 1);
//       }
//     }
//   }
//   return max;
// }

const codeA = 'a'.charCodeAt(0);

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
function longestSubstring(s, k) {
  if (k <= 1) {
    return s.length;
  }
  if (s.length < k) {
    return 0;
  }
  const cache = new Array(26).fill(0);
  let kindCount = 0;
  let standardCount = 0;
  let max = 0;
  const maxLimit = Array.from(new Set(Array.from(s))).length;
  for (let limit = 1; limit <= maxLimit; limit += 1) {
    cache.fill(0);
    kindCount = 0;
    standardCount = 0;
    let i = 0;
    let j = 0;
    for (; i < s.length; i += 1) {
      const rightCharIndex = s.charCodeAt(i) - codeA;
      cache[rightCharIndex] += 1;
      if (cache[rightCharIndex] === 1) {
        kindCount += 1;
      }
      if (cache[rightCharIndex] === k) {
        standardCount += 1;
      }
      while (kindCount > limit) {
        const leftCharIndex = s.charCodeAt(j) - codeA;
        cache[leftCharIndex] -= 1;
        if (cache[leftCharIndex] === 0) {
          kindCount -= 1;
        }
        if (cache[leftCharIndex] === k - 1) {
          standardCount -= 1;
        }
        j += 1;
      }
      if (standardCount === kindCount) {
        max = Math.max(max, i - j + 1);
      }
    }
  }
  return max;
}

console.log(longestSubstring('aaabb', 3) === 3);
console.log(longestSubstring('ababbc', 2) === 5);
